package com.xcc.dataStructures.demo03_link;

/**
 * 环形链表(约瑟夫)
 *
 * @author xiaocheng
 * @date 2020/11/22 10:57
 */
public class CircleSingleLinkedDemo {

    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.init(5);
        circleLinkedList.show();
        System.out.println("=================环形链表的长度=================");
        System.out.println(circleLinkedList.getLength());

        System.out.println("=================出圈=================");
        circleLinkedList.out(2,1);

    }

}

class CircleLinkedList {

    private CircleNode first = null;

    /**
     * 出圈
     *
     * @param step  步长
     * @param start 开始的位置
     */
    public void out(int step, int start) {
        int length = getLength();
        if (length < 1 || step < 1 || start > length) {
            System.out.println("参数不合规!");
            return;
        }
        //定义需要出圈的节点
        CircleNode cur = first;
        //需要出圈节点的前一个节点
        CircleNode pre = first;
        while (pre.next != first) {
            pre = pre.next;
        }
        //开始的位置
        for (int i = 0; i < start; i++) {
            pre = pre.next;
            cur = cur.next;
        }
        while (cur.next != cur) {
            for (int i = 0; i < step-1; i++) {
                pre = pre.next;
                cur = cur.next;
            }
            System.out.printf("出圈编号为:%d\n",cur.no);
            pre.next = cur.next;
            cur = cur.next;
        }
        System.out.printf("出圈编号为:%d\n",cur.no);
    }

    /**
     * 获取环形链表的长度
     */
    public int getLength() {
        if (first == null) {
            return 0;
        }
        int count = 1;
        CircleNode temp = first;
        while (temp.next != first) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 遍历
     */
    public void show() {
        if (first == null) {
            System.out.println("当前链表为空链表!!!");
            return;
        }
        CircleNode temp = first;
        System.out.printf("当前编号为%d\n", first.no);
        while (temp.next != first) {
            System.out.printf("当前编号为%d\n", temp.next.no);
            temp = temp.next;
        }
    }

    /**
     * 初始化环形队列
     */
    public void init(int num) {
        if (num < 1) {
            System.out.println("初始化环形链表小于1，失败!!!");
            return;
        }
        for (int i = 1; i <= num; i++) {
            CircleNode circleNode = new CircleNode(i);
            add(circleNode);
        }
    }

    /**
     * 添加node
     */
    public void add(CircleNode node) {
        if (node == null) {
            System.out.println("需要添加的节点不存在!!!");
            return;
        }
        if (first == null) {
            first = node;
            node.next = first;
        }
        CircleNode temp = first;
        while (true) {
            if (temp.next == first) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
        node.next = first;
    }

}

/**
 * 循环链表
 */
class CircleNode {

    public int no;
    public CircleNode next;

    public CircleNode(int no) {
        this.no = no;
    }

}